'''
https://leetcode.cn/problems/gas-station/description/
'''
from typing import List


class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        l, r, n = 0, 0, len(gas)
        while l < n:
            cur_gas = 0
            while cur_gas + gas[r%n] - cost[r%n] >= 0:
                if r - l + 1 == n:
                    return l
                cur_gas += gas[r%n] - cost[r%n]
                r += 1
            l = r = r + 1
        return -1

